A
求出最大值所在下标即可。时间复杂度 。
Code
#include <cstdio>
int T, n, x, v, pos;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
pos = v = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
if (x > v) v = x, pos = i;
}
printf("%d\n", pos);
}
}
B
容易发现最大值为 ,所以只需要把 和 放在最后两位即可。
若 为奇数则按照 排列。
若 为偶数则按照 排列。
容易说明这是一种最优的排列方式。
Code
#include <cstdio>
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
if (n % 2) {
printf("1 ");
for (int i = n - 2; i >= 2; i--) printf("%d ", i);
printf("%d %d\n", n - 1, n);
} else {
for (int i = n - 2; i >= 1; i--) printf("%d ", i);
printf("%d %d\n", n - 1, n);
}
}
}
C
开两个 记录一位数和两位数及以上的数的出现次数,直接计数即可。
时间复杂度 。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 2e5 + 5;
int a[N], b[N], n, ans, T;
map<int, int> s, t;
inline int count(int x) {
int ret = 0;
while (x) ret++, x /= 10;
return ret;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
ans = 0;
s.clear(), t.clear();
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] >= 10) s[a[i]]++;
else t[a[i]]++;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
if (b[i] >= 10) s[b[i]]--;
else t[b[i]]--;
}
for (auto it: s) {
int j = it.first, k = it.second;
if (k > 0) t[count(j)] += k, ans += k;
if (k < 0) t[count(j)] += k, ans -= k;
}
for (auto it: t) {
int j = it.first, k = it.second;
if (k > 0 && j != 1) ans += k;
if (k < 0 && j != 1) ans -= k;
}
printf("%d\n", ans);
}
}
D
注意到Bob永远都赢不了,那他为什么要玩这个游戏。
对于当前的一个串 ,我们分情况讨论:
若 ,则只有在两个字符相同时平局。
若 ,考虑从只有两个字符的状态添加字符转移。容易发现只有当Bob能跟Alice拿一样的字符时是平局,否则在每一轮中Alice都可以取到比Bob不劣的字符,最后一定是Alice获胜。
所以我们一直判断是否有头尾相同/头上连续两个相同/尾上连续两个相同,并调整头尾指针即可。
再注意到头尾相同的优先级要高于头尾连续相同。时间复杂度 。
Code
#include <cstdio>
#include <cstring>
const int N = 2005;
char s[N];
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", s + 1);
int l = 1, r = strlen(s + 1);
while (l <= r && s[l] == s[r]) l++, r--;
if (l > r) {
puts("Draw");
continue;
}
while (l <= r) {
if (s[l] == s[l + 1]) l += 2;
if (s[r] == s[r - 1]) r -= 2;
else break;
}
puts(l <= r ? "Alice" : "Draw");
}
}
E
待补。
F
待补。
G
待补。